309. 最佳买卖股票时机含冷冻期

Similar Question

Solution Tips

方案一: 增加冷冻期状态

问题在于昨天的卖出还是被今天的买入参考了, 增加了一个冷冻期的判断没啥用

还是状态没搞清楚, 是不是可以分成昨天有卖出和没卖出, 两种状态?

var maxProfit = function(prices) {
    // 就是股票 II 加上了冷冻期, 还是用 dp 通用解的思路处理, 只不过能参考的变了一下
    // 1. dp[i][0/1] 代表第 i 天的时候, 不持有/持有股票, 所能获得的最大现金
    // 得加状态, 如果是持有股票了, 就一定不会处于冷冻期, 只有不持有股票的时候可能处于冷冻期
    // 将不持有股票拆分成2个状态, 不持有, 处于冷冻期 / 不持有, 不处于冷冻期
    // dp[i][0/1] 不持有, dp[i][2] 持有
    const n = prices.length;
    const dp = Array.from({length: prices.length}, () => Array.from({length: 3}))
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = -prices[0];
    // 第 0 天的时候, 买入又卖出了, 导致今天处于冷冻期, 无法操作
    dp[1][1] = 0;

    for (let i = 1; i < prices.length; i++) {
        // 买入股票有冷冻期的限制, 这里需要改一下

        // 不持有股票 dp[i][0], 且不处于冷冻期
        // 可以是前一天已经持有了, 股票, 今天卖出
        // 前一天没有持有股票, 今天继续不持有
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] + prices[i]);

        // 不持有股票, 且处于冷冻期
        // 前一天没有持有股票, 今天处于冷冻期, 说明是昨天卖出的
        if (i >= 2) {
            dp[i][1] = dp[i - 2][2] + prices[i - 1];
        }

        // 持有股票, 不可能处于冷冻期
        // 昨天没有持有股票, 且处于非冷冻期, 今天买入
        // 昨天没有持有股票, 且昨天处于冷冻期, 今天买入
        // 昨天持有股票, 今天继续持有
        dp[i][2] = Math.max(...[dp[i - 1][0] - prices[i] ,dp[i - 1][1] - prices[i], dp[i - 1][2]]);
    }

    return Math.max(dp[n - 1][0], dp[n - 1][1]);
};
console.log(maxProfit([1,2,3,0,2]));

方案二: 增加是否卖出的状态

虽然还是 3 个状态, 但是定义改变之后, 看问题的视角也跟着改变了, 成功解决问题

var maxProfit = function(prices) {
    // 就是股票 II 加上了冷冻期, 还是用 dp 通用解的思路处理, 只不过能参考的变了一下
    // 1. dp[i][0/1] 代表第 i 天的时候, 有卖出和没卖出, 所能获得的最大现金
    // 还是状态没搞清楚, 是不是可以分成有卖出和没卖出, 两种状态? 看看能不能建立起状态转移方程, 如果不行就全列了
    // 还是得加一个是否持有 , 3 中状态, 那和冷冻期又有什么区别呢?
    const n = prices.length;
    const dp = Array.from({length: prices.length}, () => Array.from({length: 3}))
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = -prices[0];
    // 第 0 天的时候, 买入又卖出了, 导致今天处于冷冻期, 无法操作
    dp[1][0] = 0;

    for (let i = 1; i < prices.length; i++) {
        // 买入股票有冷冻期的限制, 这里需要改一下

        // 今天没有持有没有卖出 dp[i][0]
        // 昨天没有持有股票, 今天继续不持有, 那就一直都是 0, 没有意义, 是不是可以去掉
        // 昨天卖出了, 今天没有持有, 没有卖出
        if (i >= 2) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        }

        // 今天没有持有, 今天卖出了
        // 昨天持有了, 今天才能卖
        dp[i][1] = Math.max(dp[i - 1][2] + prices[i]);

        // 今天持有了, 今天没有卖出
        // 可能是昨天持有了, 今天继续持有
        // 昨天没有持有, 且昨天没有卖出, 今天买入
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][0] - prices[i]);
    }

    return Math.max(dp[n - 1][0], dp[n - 1][1]);
};
console.log(maxProfit([1,2,3,0,2]));

状态继续合并

var maxProfit = function(prices) {
    // 就是股票 II 加上了冷冻期, 还是用 dp 通用解的思路处理, 只不过能参考的变了一下
    // 1. dp[i][0/1] 代表第 i 天的时候, 有卖出和没卖出, 所能获得的最大现金
    // 还是状态没搞清楚, 是不是可以分成有卖出和没卖出, 两种状态? 看看能不能建立起状态转移方程, 如果不行就全列了
    // 还是得加一个是否持有 , 3 中状态, 那和冷冻期又有什么区别呢?
    const n = prices.length;
    const dp = Array.from({length: prices.length}, () => Array.from({length: 3}))
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for (let i = 1; i < prices.length; i++) {
        // 买入股票有冷冻期的限制, 这里需要改一下

        // 今天没有持有没有卖出 dp[i][0]
        // 昨天没有持有股票, 今天继续不持有, 那就一直都是 0, 没有意义, 是不是可以去掉
        // 昨天卖出了, 今天没有持有, 没有卖出
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

        if (i >= 2) {
            // 前天没有持有的状态, 就包括了当天卖出了, 这样昨天就是冷冻期, 不影响今天买入
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
        }
        else {
            dp[i][1] = Math.max(-prices[0], -prices[1]);
        }
    }

    return Math.max(dp[n - 1][0], dp[n - 1][1]);
};

确实是 ok 的, 有人表示就和打家劫舍是一样的